﻿//   1、水果成篮
//class Solution {
//public:
//    int totalFruit(vector<int>& fruits)
//    {
//        int left = 0, right = 0;
//        int max = 0;
//        int n = fruits.size();
//        unordered_map<int, int> hash;
//        while (n > right)
//        {
//            hash[fruits[right]]++;
//            while (hash.size() > 2)
//            {
//                hash[fruits[left]]--;
//                if (hash[fruits[left]] == 0)
//                    hash.erase(fruits[left]);
//                left++;
//            }
//            max = fmax(max, right - left + 1);
//            right++;
//        }
//        return max;
//    }
//};

//   2、找到字符串中所有字母异位词
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p)
//    {
//        vector<int> ret;
//        int left = 0, right = 0;
//        int hash1[26] = { 0 };
//        for (auto ch : p)
//        {
//            hash1[ch - 'a']++;
//        }
//        int hash2[26] = { 0 };
//        int m = p.size(), count = 0;
//        while (s.size() > right)
//        {
//            char in = s[right];
//            hash2[in - 'a']++;
//            if (hash2[in - 'a'] <= hash1[in - 'a']) count++;  //进窗口 维护
//            if (right - left + 1 > m)
//            {
//                char out = s[left++];
//                if (hash2[out - 'a'] <= hash1[out - 'a']) count--;  //出窗口
//                hash2[out - 'a']--;  //维护
//            }
//            if (count == m) ret.push_back(left);
//            right++;
//        }
//        return ret;
//    }
//};

//3、串联所有单词的子串

//class Solution
//{
//public:
//    vector<int> findSubstring(string s, vector<string>& words)
//    {
//        vector<int> ret;
//        unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
//        for (auto& s : words) hash1[s]++;
//        int len = words[0].size(), m = words.size();
//        for (int i = 0; i < len; i++) // 执⾏ len 次
//        {
//            unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
//            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
//            {
//                // 进窗⼝ + 维护 count
//                string in = s.substr(right, len);
//                hash2[in]++;
//                if (hash1.count(in) && hash2[in] <= hash1[in]) count++;
//                // 判断
//                if (right - left + 1 > len * m)
//                {
//                    // 出窗⼝ + 维护 count
//                    string out = s.substr(left, len);
//                    if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
//                    hash2[out]--;
//                    left += len;
//                }
//                // 更新结果
//                if (count == m) ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};

//4、最小覆盖字串
//class Solution
//{
//public:
//    string minWindow(string s, string t)
//    {
//        int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
//        int kinds = 0; // 统计有效字符有多少种
//        for (auto ch : t)
//            if (hash1[ch]++ == 0) kinds++;
//        int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
//        int minlen = INT_MAX, begin = -1;
//        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
//        {
//            char in = s[right];
//            if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
//            while (count == kinds) // 判断条件
//            {
//                if (right - left + 1 < minlen) // 更新结果
//                {
//                    minlen = right - left + 1;
//                    begin = left;
//                }
//                char out = s[left++];
//                if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
//            }
//        }
//        if (begin == -1) return "";
//        else return s.substr(begin, minlen);
//    }
//};